#include "vector.hpp"
#include <iostream>
#include <algorithm>

namespace STL
{
    template <class T, class Container = STL::vector<T>,
              class Compare = std::less<T>>
    class priority_queue
    {
    public:
        priority_queue()
            : _size(0)
        {
        }

        T top()
        {
            assert(!empty());
            return _data[0];
        }

        void up_update(int pos)
        {
            // std::cout << "up_updata: " << pos << std::endl;
            while (pos > 0 && _compare(_data[pos], _data[parentpos(pos)]))
            {
                // std::cout << "num" << _data[pos] << "->num" << _data[parentpos(pos)] << std::endl;
                std::swap(_data[pos], _data[parentpos(pos)]);
                pos = parentpos(pos);
            }
        }

        void down_update(int pos)
        {
            while (leftchild(pos) < _size)
            {
                // 记录最值的位置
                int extreme_pos = pos;
                // 看看左子几点是否是最值
                extreme_pos = (_compare(_data[leftchild(pos)], _data[pos])
                                   ? leftchild(pos)
                                   : extreme_pos);
                if (rightchild(pos) < _size)
                    extreme_pos = (_compare(_data[rightchild(pos)], _data[extreme_pos])
                                       ? rightchild(pos)
                                       : extreme_pos);
                if (extreme_pos == pos)
                    return;
                else
                {
                    std::swap(_data[pos], _data[extreme_pos]);
                    pos = extreme_pos;
                }
            }
        }

        void push(const T &val)
        {
            _data.push_back(val);
            _size += 1;
            // std::cout << "----------_size - 1----------" << _size-1 << std::endl;
            up_update(_size - 1);
        }

        T pop()
        {
            assert(!empty());
            T ret_val = _data[0];
            _data[0] = _data[_size - 1];
            _data.pop_back();
            _size -= 1;
            down_update(0);
            return ret_val;
        }

        bool empty()
        {
            return _size == 0;
        }


        int parentpos(int child)
        {
            return (child - 1) >> 1;
        }

        int leftchild(int parent)
        {
            return (parent << 1) + 1;
        }

        int rightchild(int parent)
        {
            return (parent << 1) + 2;
        }

        size_t size()
        {
            return _size;
        }

        void print()
        {
            for (size_t i = 0; i < _size; i++)
            {
                std::cout << _data[i] << " ";
            }
            std::cout << std::endl;
        }

        ~priority_queue()
        {}

    private:
        Container _data;
        Compare _compare;
        size_t _size;
    };
}